As the importance of protecting personal information and confidential information increases, a market of services using these information has been currently expanding. Examples of such services include a service utilizing position information of an individual user, which can be obtained with a smartphone. Accordingly, attention is paid on confidentiality techniques that can utilize data of protected personal information and confidential information unchanged. Confidentiality techniques include techniques using an encryption technique and a statistical technique according to a data type and a service requirement.
Confidentiality techniques using an encryption technique include a homomorphic encryption technique. The homomorphic encryption technique is one of public key cryptosystems using a pair of different keys for encryption and decryption, and has a function of enabling an operation of encrypted data unchanged.
By using the homomorphic encryption scheme, encrypted text resultant from an addition or multiplication operation can be obtained by performing an arithmetic operation such as an addition or a multiplication without decoding the encrypted text. Expectations have been rising for the use of this property of the homomorphic encryption in electronic voting and electronic cash fields and a recent cloud coMPUting field. RSA encryption scheme that enables only a multiplication, and Additive ElGamal encryption that enables only an addition are known as homomorphic encryption scheme for an addition and a multiplication. Assuming that encrypted texts of plaintexts (messages) a and b are E(a) and E(b), an encrypted text E(a·b) of a product a·b of the plaintexts can be calculated from E(a) and E(b) with multiplicative homomorphic encryption. Moreover, assuming that encrypted texts of plaintexts (messages) a and b are E(a) and E(b), an encrypted text E(a+b) of a sum a+b of the plaintexts can be calculated from E(a) and E(b) with additive hohomorphic encryption. By using the homomorphic encryption scheme, an encrypted text resultant from an arithmetic operation such as an addition or a multiplication can be obtained with an addition or a multiplication of encrypted texts without decrypting the encrypted texts. Expectations have been growing for the use of this property of homomorphic encryption in electronic voting and electronic cash fields, and a recent cloud coMPUting field.
Fully homomorphic encryption has been recently known as encryption having homomorphism for both an addition and a multiplication. If an addition and a multiplication can be performed for encrypted texts unchanged, an arithmetic operation such as an exclusive OR, a logical AND, or a negation can be performed for the encrypted texts unchanged. Namely, fully homomorphic encryption is encryption having homomorphism for arithmetic operations performed by all logic circuits. At first, only logical implementation methods were announced and practical configuration methods were not disclosed. However, not only specific configuration examples of key generation methods but encryption schemes that expand types of data that can be encrypted have been proposed. Moreover, somewhat homomorphic encryption that can perform both an addition and a multiplication by a limited number of times is present. Since this encryption scheme needs far less encryption size and processing performance than those of fully homomorphic encryption, more practical operations are expected.
Generally, an encryption technique is used in a system for verifying similarity between two information. Examples of such a system include a biometric authentication system and a tag search system.    [Patent Document 1] Japanese Laid-open Patent Publication No. 2011-145512    [Non-patent Document 1] C. Gentry, “Fully Homomorphic encryption using ideal lattices”, STOC2009, pp. 169-178, 2009    [Non-patent Document 2] C. Gentry and S. Halevi, “Implementing Gentry's Fully Homomorphic Encryption Scheme”, EUROCRYPT 2011, LNCS 6632, pp. 129-148, 2011    [Non-Patent Document 3] Yasuda, Yajima, Shimoyama, and Kogure, “Cloud secure summation of purchase history data possessed by a plurality of enterprises”, SCIS 2012